20240619 2713 - Hard - Dp

2713. Maximum Strictly Increasing Cells in a Matrix

Original Solution, DP, TLE

剪枝还差点意思

• 可以考虑排序

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])

        @cache
        def dp(i, j):
            cnt = 1
            # minRowN = mat[i][j]
            minRowN = mat[i][j]
            tmpi2 = i
            for i2 in range(m):
                if mat[i2][j] < minRowN and mat[i][j] < mat[i2][j]:
                    tmpi2 = i2
                    minRowN = mat[i2][j]
            if tmpi2 != i:
                cnt = max(dp(tmpi2, j) + 1, cnt)
            # for i2 in range(m):
            #     # pruning
            #     if i2 != i and mat[i][j] < mat[i2][j]:
            #         cnt = max(dp(i2, j) + 1, cnt)
            for j2 in range(n):
                # pruning
                if j2 != j and mat[i][j] < mat[i][j2]:
                    cnt = max(dp(i, j2) + 1, cnt)
            return cnt
            
        res = 1
        for i in range(m):
            # minN = mat[i][0]
            for j in range(n):
                # if mat[i][j] <= minN:
                    # minN = mat[i][j]
                res = max(dp(i, j), res)
        return res

灵神思路，自底向上的思路

• 从小到大排序所有元素，并且记录把每个元素放到哈希表里
  • 如下的 g := map[int][]pair{} 和 slices.Sort(keys)
• 从小到大遍历所有元素，逐步更新 rowMax 和 colMax。

func maxIncreasingCells(mat [][]int) int {
    type pair struct{ x, y int }
    g := map[int][]pair{}
    for i, row := range mat {
        for j, x := range row {
            g[x] = append(g[x], pair{i, j}) // 相同元素放在同一组，统计位置
        }
    }
    keys := make([]int, 0, len(g))
    for k := range g {
        keys = append(keys, k)
    }
    slices.Sort(keys)

    rowMax := make([]int, len(mat))
    colMax := make([]int, len(mat[0]))
    for _, x := range keys {
        pos := g[x]
        // 先把所有 f 值都算出来，再更新 rowMax 和 colMax
        fs := make([]int, len(pos))
        for i, p := range pos {
            fs[i] = max(rowMax[p.x], colMax[p.y]) + 1
        }
        for i, p := range pos {
            rowMax[p.x] = max(rowMax[p.x], fs[i]) // 更新第 p.x 行的最大 f 值
            colMax[p.y] = max(colMax[p.y], fs[i]) // 更新第 p.y 列的最大 f 值
        }
    }
    return slices.Max(rowMax)
}